package com.leetcode.周赛.第235场;

import java.util.Arrays;

/**
 * @author: xiaomi
 * @date: 2021/4/4
 * @description: 5724. 绝对差值和
 * https://leetcode-cn.com/contest/weekly-contest-235/problems/minimum-absolute-sum-difference/
 */
public class B_5724_绝对差值和 {

    static B_5724_绝对差值和 action = new B_5724_绝对差值和();

    public static void main(String[] args) {
//        int[] nums = new int[]{1, 2, 3, 6};
//        //action.binarySearchMin(0, nums, 4);//begin
//        int res = action.binarySearchMin(4, nums, 4);

        test1();
        test2();
        test3();
    }

    static void test1() {
        //
        int[] nums1 = new int[]{1, 7, 5};
        int[] nums2 = new int[]{2, 3, 5};
        int res = action.minAbsoluteSumDiff(nums1, nums2);

        System.out.println("res = " + res);
    }

    static void test2() {
        //

        //System.out.println("res = " + res);
    }

    static void test3() {
        //

        //System.out.println("res = " + res);
    }

    /**
     * 二分查找
     *
     * @param nums1
     * @param nums2
     * @return
     */
    public int minAbsoluteSumDiff(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int[] absArr = new int[n];
        long sum = 0;
        for (int i = 0; i < n; i++) {
            absArr[i] = Math.abs(nums1[i] - nums2[i]);
            sum += absArr[i];
        }
        Arrays.sort(nums1);
        int max = 0;
        for (int i = 0; i < n; i++) {
            int temp = binarySearchMin(nums2[i], nums1, n);
            max = Math.max(max, absArr[i] - temp);
        }
        return (int) ((sum - max) % 1000000007);
    }

    /**
     * 返回最小绝对值差值
     *
     * @param value
     * @param nums1
     * @param n
     * @return
     */
    private int binarySearchMin(int value, int[] nums1, int n) {
        int begin = 0, end = n;
        int mid = n >> 1;
        while (begin < end) {
            if (nums1[mid] == value) {
                return 0;
            }
            if (nums1[mid] < value) {
                begin = mid + 1;
            } else {
                end = mid;
            }
            mid = (begin + end) >> 1;
        }
        if (begin == n) {
            return Math.abs(nums1[n - 1] - value);
        }
        if (nums1[begin] < value) {
            if (begin == n - 1) {
                return value - nums1[begin];
            } else {
                return Math.min(value - nums1[begin], nums1[begin + 1] - value);
            }
        } else {
            if (begin == 0) {
                return nums1[begin] - value;
            } else {
                return Math.min(value - nums1[begin - 1], nums1[begin] - value);
            }
        }

    }

}
